package 滑动窗口And双指针;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/1/10 11:44
 */
public class leetocde881救生艇 {

    /*
     贪心 + 滑动窗口And双指针.双指针！
     */


    /*
     就说 这个 贪心策略 不太正确
     错误的 basecase 实列
     people = [5,1,4,2]
     limit  = 6
     */
    public int solution(int []nums,int limit){
        int count = 0;
        Arrays.sort(nums);
        for(int i = 0;i < nums.length;){
            int sum = 0;
            while(i < nums.length && (sum += nums[i]) <= limit){
                    i++;
            }
            count++;
        }
        return count;
    }





    /*
     换种贪心的 策略
     排序
     每次 从 头 和 尾 挑一个
     让最重的和最轻的 ，这样的组合
     O（N * lgN）
     */
    public int solution1(int []nums,int limit){
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        int count = 0;
        /*
         left == right 的时候
         也不用 进行特殊的判断， 直接 通用下面的 while 循环就行
         ，简单 分析一下就明白为什么了！
         */
        while(left <= right){
            if(nums[right] + nums[left] <= limit){
                left++;
//                right--;
            }
                count++;
                right--;
        }
        return count;
    }

    /*
     最优解 使 桶排序的 思想
     */


}
